package com.gthncz;

import java.util.*;

public class Demo13 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N, K;
        N = sc.nextInt();
        K = sc.nextInt();

        Map<String, Integer> strTimes = new HashMap<String, Integer>();
        Map<Integer, Set<String>> timesStrs = new HashMap<Integer, Set<String>>();

        String tmp ;
        for (int i=0; i<N; ++i)  {
            tmp = sc.next();
            // System.out.println(tmp);
            strTimes.putIfAbsent(tmp, 0);
            int times = strTimes.get(tmp);
            strTimes.put(tmp, times+1);

            if (times > 0) {
                timesStrs.get(times).remove(tmp);
            }
            timesStrs.putIfAbsent(times+1, new HashSet<>());
            timesStrs.get(times+1).add(tmp);
        }

//        System.out.println(strTimes);
//        System.out.println(timesStrs);

        Integer[] times = strTimes.values().toArray(new Integer[0]);

        Arrays.sort(times); // 升序
        // 前 K 大
        int k= K;
        for(int i=times.length-1; i>=0 && k>0; --i) {
            Set<String> strSet = timesStrs.get(times[i]);
            String[] strs = strSet.toArray(new String[0]);
            Arrays.sort(strs, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    int len1 = o1.length();
                    int len2 = o2.length();
                    int i, j;
                    for(i=0, j=0; i<len1 && j<len2; ++i, ++j) {
                        if (o1.charAt(i) != o2.charAt(j)) {
                            return o1.charAt(i) - o2.charAt(j);
                        }
                    }
                    return len1 - len2;
                }
            });
            for (String str: strs) {
                if (k-- > 0) {
                    System.out.printf("%s %d\n", str, times[i]);
                } else {
                    break;
                }
            }
        }

        // 前 K 小
        k = K;
        for(int i=0; i<times.length && k>0; ++i) {
            Set<String> strSet = timesStrs.get(times[i]);
            String[] strs = strSet.toArray(new String[0]);
            Arrays.sort(strs, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    int len1 = o1.length();
                    int len2 = o2.length();
                    int i, j;
                    for(i=0, j=0; i<len1 && j<len2; ++i, ++j) {
                        if (o1.charAt(i) != o2.charAt(j)) {
                            return o1.charAt(i) - o2.charAt(j);
                        }
                    }
                    return len1 - len2;
                }
            });
            for (String str: strs) {
                if (k-- > 0) {
                    System.out.printf("%s %d\n", str, times[i]);
                } else {
                    break;
                }
            }
        }
    }

}
